Skip to main content

Magic Number

Problem Description​

A magic number is defined as a number that can be expressed as a power of 5 or sum of unique powers of 5. First few magic numbers are 5, 25, 30(5 + 25), 125, 130(125 + 5), … Given the value of n, find the n'th Magic number modulo 109+7.

Examples​

Example 1:

Input: n = 1
Output: 5
Explanation: 1'st Magic number is 5.

Example 2:

Input: n = 2
Output: 25
Explanation: 2'nd Magic number is 25.

Your Task​

You don't need to read input or print anything. Your task is to complete the function nthMagicNo() which takes n input and returns the answer with modulo 10^9+7.

Expected Time Complexity: O(log(n))O(log(n))

Expected Auxiliary Space: O(1)O(1) for iterative approach.

Constraints​

  • 1 ≤ n ≤ 10^5

Problem Explanation​

A magic number is defined as a number that can be expressed as a power of 5 or sum of unique powers of 5. First few magic numbers are 5, 25, 30(5 + 25), 125, 130(125 + 5), … Given the value of n, find the n'th Magic number modulo 109+7.

Code Implementation​

Written by @Ishitamukherjee2004
def get_nth_magic_number(n):
magic_numbers = []
power = 0
while len(magic_numbers) < n:
num = 5 ** power
magic_numbers.append(num)
for i in range(len(magic_numbers) - 1):
magic_numbers.append(num + magic_numbers[i])
power += 1
return magic_numbers[n - 1] % (10**9 + 7)

n = int(input("Enter the value of N: "))
print("The {}th magic number is: {}".format(n, get_nth_magic_number(n)))


Time Complexity​

  • The iterative approach has a time complexity of O(nlogn)O(n log n).

Space Complexity​

  • The space complexity is O(n)O(n) since we are using only a fixed amount of extra space.